"first of May," on which the opening of the season of flowers and fruit formerly was celebrated throughout Europe, mid-13c.; see May + day (n.). May Queen "girl or young woman crowned with flowers and honored as queen at the games held on May Day," seems to be a Victorian re-invented tradition; the phrase Queen of Maij is attested from c. 1500.
May Day's association with communism (and socialism and anarchism) dates to 1890. A U.S. general strike for an eight-hour workday began May 1, 1886, and culminated in the Haymarket bombing affair in Chicago on May 4. By 1890 strikes, protests, and rallies were being held in Europe by socialist and labor organizations on May 1, at first in support of the eight-hour day, more or less in commemoration of the 1886 strike.